/**王宏伟 计84 2008010486
 * 个体编码说明：用数组表示一个方案。
 * 例如：J、I、H、G、F、E、D、C、B、A用数组表示为：9、8、7、6、5、4、3、2、1、0。
 * 
 * 交配方案：常规交配法，一对父代产生一对子代。
 * 
 * 变异方法：随机产生一个小于种群规模的一个数，然后产生两个随机的不同的小于城市数目的数，然后交换数组内的城市。
 * 例如：种群规模为100000，产生了一个3000的数，然后产生4、8，所以对3000下标为4和8里所含有的城市进行交换。
 * 
 * 新种群构成的方法：交配后产生的子代和原有的父代都在原来的种群种，然后进行计算每个个体的适应值、选择概率。
 * 每个个体在新种群中出现的次数是选择概率乘以固定的种群规模。
 * 
 * 算法结束的条件：最佳值保持连续groupGen代，则停止。
 * 
 * 说明：如果此种参数得到的效果较差，那么请把 N = 100000；groupGen = 20； PC = 0.3 ； PM = 0.4；
 * 
 * */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

float func(int n,float *cityX,float *cityY,int *rank) ///适应函数
{
	float t = 0;
	int i,r,s;
	for(i = 0;i < n-1;i++){
		r = rank[i];
		s = rank[i + 1];
		t += sqrtf((cityX[s]-cityX[r])*(cityX[s]-cityX[r])+(cityY[s]-cityY[r])*(cityY[s]-cityY[r]));
	}
	r = rank[0];
	s = rank[n-1];
	t += sqrtf((cityX[s]-cityX[r])*(cityX[s]-cityX[r])+(cityY[s]-cityY[r])*(cityY[s]-cityY[r]));
	return t;
}

void exchange(int a,int b,int *rank) ///变异时用到的交换函数
{
	int t = rank[a]; rank[a] = rank[b]; rank[b] = t;
}

void groupInit(int **group,int N,int n) ///种群初始化函数
{
	int *temp = malloc(sizeof(int)*n);
	int i,j,t;
	for(i = 0;i < N;i++)
	{
		for(j = 0;j < n;j++)
			temp[j] = 0;		
		for(j = 0;j < n;j++)
		{
			do
			{
				t = rand()%n;
			}while(temp[t] == 1);
			group[i][j] = t;
			temp[t] = 1;
		}
	}
}

void groupBirth(int n,int **group,int a,int b,int k) ///交配函数
{
	int i,j;
	int *temp = malloc(sizeof(int)*n);
	for(i = 0;i < n;i++)
		temp[i] = 0;
	for(i = 0;i < n/2;i++)
	{
		group[k][i] = group[a][i];
		temp[group[a][i]] = 1;
	}
	j = 0;
	for(i = n/2;i < n;i++)
	{
		while(temp[group[b][j]]) j++;
		group[k][i] = group[b][j];
		temp[group[b][j]] = 1;
		j++;
	}
	
	for(i = 0;i < n;i++)
		temp[i] = 0;
	for(i = 0;i < n/2;i++)
	{
		group[k+1][i] = group[b][i];
		temp[group[b][i]] = 1;
	}
	j = 0;
	for(i = n/2;i < n;i++)
	{
		while(temp[group[a][j]]) j++;
		group[k+1][i] = group[a][j];
		temp[group[a][j]] = 1;
		j++;
	}
}

int main(int arc,char **argv) ///主函数
{
	int n,i,j,k,N = 7000; // !!!
	FILE *read = fopen(argv[1],"r");
	FILE *write = fopen(argv[2],"w");
	///输入
	fscanf(read,"%d",&n);
	char **cityName = malloc(sizeof(char*)*n);
	float *cityX = malloc(sizeof(float)*n);
	float *cityY = malloc(sizeof(float)*n);
	for(i = 0;i < n;i++)
	{
		cityName[i] = malloc(sizeof(char)*10);
		fscanf(read,"%s\t%f\t%f\n",cityName[i],&cityX[i],&cityY[i]);
	}
	int **group = malloc(sizeof(int*)*2*N);	
	int **groupTemp = malloc(sizeof(int*)*2*N);	
	float *groupFunc = malloc(sizeof(float)*2*N);
	int *groupPer = malloc(sizeof(int)*2*N);
	for(i = 0;i < 2*N;i++)
	{	
		group[i] = malloc(sizeof(int)*n);
		groupTemp[i] = malloc(sizeof(int)*n);
	}
	int *top;
	int topConti = 0;
	int groupTopNum = N;
	int groupGen = 40; // !!!
	float groupValueMax = 0;
	float topValue = 10000;
	float topBeforeValue = 10000;
	float pc = 0.2,pm = 0.4,funcAll = 0; // !!!
	///初始化
	groupInit(group,N,n);
	for(i = 0;i < N;i++)
	{
		float temp = func(n,cityX,cityY,group[i]);
		if(temp > groupValueMax)
			groupValueMax = temp;
	}
	while(topConti < groupGen)///如果最佳值连续groupGen代相同，那么结束。
	{
		topBeforeValue = topValue;
		for(i = 0;i < groupTopNum;i++)
			for(j = 0;j < n;j++)
				groupTemp[i][j] = group[i][j];
		///以下计算适应值
		for(i = 0;i < groupTopNum;i++)
		{
			groupFunc[i] = func(n,cityX,cityY,group[i]);
			if(groupFunc[i] < topValue)
			{	
				topValue = groupFunc[i];
				top = group[i];
			}
			funcAll += pow(2,groupValueMax-groupFunc[i]);
		}
		for(i = 0;i < groupTopNum;i++)
		{
			groupPer[i] = (int)(pow(2,groupValueMax-groupFunc[i])/funcAll * N + 0.5);
		}
		int t = 0;
		///以下产生新种群
		for(i = 0;i < groupTopNum;i++)
		{
			for(j = 0;j < groupPer[i];j++)
			{
				if(t+j >= N)
					break;
				for(k = 0;k < n;k++)
					group[t+j][k] = groupTemp[i][k];
			}
			t += groupPer[i];
		}
		groupTopNum = N;
		///以下是交配过程
		for(i = 0;i < (int)(pc*N);i++)
		{
			int a,b;
			do
			{
				a = rand()%N;
				b = rand()%N;
			}while(a == b);
			groupBirth(n,group,a,b,groupTopNum);
			groupTopNum += 2;
		}
		///以下是变异过程
		for(i = 0;i < (int)(pm*groupTopNum);i++)
		{
			int a,b,c;
			a = rand()%groupTopNum;
			do
			{
				b = rand()%n;
				c = rand()%n;				
			}while(b == c);
			exchange(b,c,group[a]);
		}
		if(topValue <= topBeforeValue)
			topConti ++;
		else
			topConti = 0;
	}
	///输出
	for(i = 0;i < n;i++)
		fprintf(write,"%s ",cityName[top[i]]);
	fprintf(write,"%f\n",topValue);
	return 0;
}	
